'''
例 7 拟分配 n 人去干 n 项工作,每人干且仅干一项工作,若分配第 i 人去干第 j
项工作,需花费 c ij 单位时间,问应如何分配工作才能使工人花费的总时间最少?

设xij,xij为1表示i工作派给j做,否则为0
目标函数:
    min z=xij*cij (i=1,2,...,n  j=1,2,...,n)
约束条件：
    #一件事(i)由一个人做
    sum(xij)=1 (j=1,2,...,n)
    #一个人(j)做一件事
    sum(xij)=1 (i=1,2,...,m)
    xij=1或xij=0

指派问题实际上就是特殊的运输问题： 即当m=n ai=bj=1
'''

# 代码略，基础线性规划
'''
解决指派问题的匈牙利算法
例如系数矩阵  [
                [16 15 19 22]
                [17 21 19 18]
                [24 22 18 17]
                [17 19 22 16]
            ]
横轴表示第i个人，纵轴表示第j项工作
匈牙利算法：
    每一行每个元素减去这一行最小元素，得到的矩阵中，那一列没有0的，将这一列的每个元素减去这一列最小元素
    最终得到0的位置就是结果，例如：
    [
        [1 0 4 7]
        [0 4 2 1]
        [7 5 1 0]
        [1 3 6 0]
    ]
    得到最优指派为：
    [
        [1 2 3 4]
        [2 1 3 4]
    ]
    即1-4这4个人所对应指派的人物标号[2,1,3,4]
但这种方法有一个问题，比如
    [
        [3 5]
        [3 5]
    ]
就得不到正确答案，这里正确的做法是加上一个随机扰动，不过一般不会出现这种情况
还有一种情况是人和任务的数量不一致，这时候可以补充一些人或人物使整一行或整一列值相等即可

python中调用scipy.optimize.linear_sum_assignment()解决问题,pyhon大法好
'''
from scipy.optimize import linear_sum_assignment
import numpy as np

cost = np.array([[16, 15, 19, 22],
                 [17, 21, 19, 18],
                 [24, 22, 18, 17],
                 [17, 19, 22, 16]])
row_ind, col_ind = linear_sum_assignment(cost)
# row_ind表示列索引(1-n人)
# python索引从0开始,所以加1
print(row_ind+1)
# col_ind表示选取的元素在每一行的索引
print(col_ind+1)
# 取出的元素
print(cost[row_ind, col_ind])
# 求出总和
print(cost[row_ind, col_ind].sum())

# 例子2
cost2=np.array([[12,7,9,7,9],
                [8,9,6,6,6],
                [7,17,12,14,12],
                [15,14,6,6,10],
                [4,10,7,10,6]])
row_ind2, col_ind2 = linear_sum_assignment(cost2)
# row_ind表示列索引(1-n人)
# python索引从0开始,所以加1
print(row_ind2+1)
# col_ind表示选取的元素在每一列的索引
print(col_ind2+1)
# 取出的元素
print(cost2[row_ind2, col_ind2])
# 求出总和
print(cost2[row_ind2, col_ind2].sum())